package com.xmg.dataStructure.digui;

import java.util.ArrayList;
import java.util.List;

/**
 * 迷宫递归回溯算法实现
 * 地图 0：没走过  1：墙  2：成功路径  3：失败路径
 *
 * 最短路径设计：
 *      遍历所有策略，计算最小步数方案，记录下来 共24种
 *      上 右 下 左
 *      上 右 左 下
 *      上 下 左 右
 *      上 下 右 左
 *      上 左 下 右
 *      上 左 右 下
 *      。。。
 *
 */
public class Migong {
    public static int stepNums = 0;
    public static int[][] minMap = new int[7][6];
    public static int minStep = 0;
    public static void main(String[] args) {
        int[][] map = initMap();

        List<int[][]> celue = new ArrayList<>();
        int[][] celue1 = {{-1,0},{0,1},{1,0},{0,-1}};
        int[][] celue2 = {{-1,0},{0,1},{0,-1},{1,0}};
        int[][] celue3 = {{-1,0},{1,0},{0,1},{0,-1}};
        int[][] celue4 = {{-1,0},{1,0},{0,-1},{0,1}};
        int[][] celue5 = {{-1,0},{0,-1},{1,0},{0,1}};
        int[][] celue6 = {{-1,0},{0,-1},{0,1},{1,0}};

        celue.add(celue1);
        celue.add(celue2);
        celue.add(celue3);
        celue.add(celue4);
        celue.add(celue5);
        celue.add(celue6);

        System.out.println("原始迷宫");
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 6; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

//        setway(map,1,1);
//        System.out.println("走出后的迷宫");
//        for (int i = 0; i < 7; i++) {
//            for (int j = 0; j < 6; j++) {
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
//
//        System.out.printf("共行走了{%d}步",stepNums);

        for (int i = 0; i < celue.size(); i++) {
            int[][] myMap = initMap();
            stepNums = 0;
            if(setway2(myMap,1,1,celue.get(i))){
                if(minStep==0 || stepNums<minStep){
                    minStep = stepNums;
                    minMap = myMap;
                }
            }

        }

        System.out.printf("最短路径行走了{%d}步",minStep);
        System.out.println("最短路径迷宫");
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 6; j++) {
                System.out.print(minMap[i][j] + " ");
            }
            System.out.println();
        }
    }

    static int[][] initMap(){
        int[][] map = new int[7][6];
        for (int i = 0; i < 6; i++) {
            map[0][i] = 1;
            map[6][i] = 1;
        }

        for (int i = 0; i<7;i++){
            map[i][0] = 1;
            map[i][5] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
        map[3][3] = 1;
        map[2][3] = 1;

        return map;
    }

    /**
     * 递归回溯寻找迷宫路线
     * @param map 迷宫地图
     * @param i 行
     * @param j 列
     * @return 此位置是否可走
     * 默认行走策略  下->右->上->左
     */
    public static boolean setway(int[][] map,int i,int j){
        if (map[5][4]==2){
            return true;
        }else{
            if(map[i][j]==0){//当前位置没有走过
                map[i][j] = 2;
                if(setway(map,i+1,j)){
                    stepNums++;
                    return true;
                }else if(setway(map,i,j+1)){
                    stepNums++;
                    return true;
                }else if(setway(map,i-1,j)){
                    stepNums++;
                    return true;
                }else if(setway(map,i,j-1)){
                    stepNums++;
                    return true;
                }else{
                    map[i][j] = 3;
                    return false;
                }
            }else{
                return false;
            }
        }
    }


    public static boolean setway2(int[][] map,int i,int j,int[][] celue){
        if (map[5][4]==2){

            return true;
        }else{
            if(map[i][j]==0){//当前位置没有走过
                map[i][j] = 2;
                if(setway2(map,i+celue[0][0],j+celue[0][1],celue)){
                    stepNums++;
                    return true;
                }else if(setway2(map,i+celue[1][0],j+celue[1][1],celue)){
                    stepNums++;
                    return true;
                }else if(setway2(map,i+celue[2][0],j+celue[2][1],celue)){
                    stepNums++;
                    return true;
                }else if(setway2(map,i+celue[3][0],j+celue[3][1],celue)){
                    stepNums++;
                    return true;
                }else{
                    map[i][j] = 3;
                    return false;
                }
            }else{
                return false;
            }
        }
    }
}
